import scala.collection.mutable._
/*
def getMin(denom:List[Int],sum:Int):Int= {
    var xs=new Array[Int](sum+1)
    for(d <- denom) {
        xs(d)=1
    }
    def getMin1(sum:Int):Int= {
        if(sum<=0) -1
        else if(xs(sum)!=0) {xs(sum)} 
            else {
                var BestSoFar=Int.MaxValue
                for(d <-denom) {
                   // println((d,sum-d,a))
                    var thisOne=getMin1(sum-d)
                    var thisTwo=getMin1(d)
                    if(  (thisOne!=(-1) && thisTwo!=(-1)) && thisOne + thisTwo < BestSoFar) {
                        BestSoFar=thisOne + thisTwo
                    }
                }
                if(BestSoFar==Int.MaxValue) BestSoFar= (-1)                
                xs(sum)=BestSoFar
                //print(BestSoFar)
                BestSoFar
            }
        }
    getMin1(sum)
}

test("this is the required number of coins") {
    getMin(List(),4) should equal(-1)
    getMin(List(4),4) should equal (1)
    getMin(List(2,3),50) should equal (17)
    getMin(List(5,4,1),12) should equal (3)
}
*/

/**def getCount(a:Int,den:List[Int]):Array[Int]= {
    if(den==Nil){
        null
    }
    else if(a==0) null 
    else {
        var xs=Array[Int](den.length)
        def find(a:Int,b:List[Int]):Int= {
            if(b.head==a) 0
            else 1 + find(a,b.tail)
        }
        def min(b:List[Int]):Int= {
            var min=Integer.MAX_VALUE
            for(i<-b) {
               min=Math.min(min,i) 
            }
            min
        }
        def getCount1(a:Int,den:List[Int]):Array[Int]= { //12 5,4,1
                var y=getMin(den,a) 
                var i=0
                while(i!=y) {
                   var tupList=den map ((x) => (x,a-x)) //(5,7)(4,8)1,11
                   var eachGet=tupList map ((j) => getMin(den,j._1) + getMin(den,j._2))
                   var least=min(eachGet)
                   println(least,eachGet,den.length)
                   xs(find(least,den))=xs(find(least,den))+1
                   i+=1
                }
                xs
        }
        getCount1(a,den)      
    }
}
 println(getCount(12,List(5,4,1)))
 */
def getMinAndDenom(denom:Array[Int],sum:Int):(Int,Array[Int])= {
    var memoMin=new Array[Int](sum+1)
    var memoDen=new Array[Array[Int]](sum+1)
    for(d <- denom) {
        memoMin(d)=1
        memoDen(d)=new Array[Int](denom.length)
        memoDen(d)(find(d,denom))=1
    }
   def find(a:Int,b:Array[Int]):Int= {
       for(i<-0 until b.length) {
           if(b(i)==a) return i
       }
       return -1
   }
   def addArrays(xs:Array[Int],ys:Array[Int]):Array[Int]= {
       var zs=new Array[Int](xs.length)
       for(i<-0 until zs.length) {zs(i)=xs(i) + ys(i)}
       zs
   } 
   def getMin1(sum:Int):(Int,Array[Int])= {
        if(sum<=0) (-1,null)
        else if(memoMin(sum)!=0) {(memoMin(sum),memoDen(sum))} 
            else {
                var BestSoFar=Int.MaxValue
                var BestArray:Array[Int]=null
                for(d <-denom) {
                   // println((d,sum-d,a))
                    var thisOne=getMin1(sum-d)
                    var thisTwo=getMin1(d)
                    if((thisOne._1!=(-1) && thisTwo._1!=(-1) && thisOne._1 + thisTwo._1 < BestSoFar) {
                        BestSoFar=thisOne._1 + thisTwo._1
                        BestArray=addArrays(thisOne._2,thisTwo._2)
                    }
                }
                if(BestSoFar==Int.MaxValue) BestSoFar= (-1)                
                memoMin(sum)=BestSoFar
                memoDen(sum)=BestArray
                //print(BestSoFar)
                (BestSoFar,BestArray)
            }
        }
    getMin1(sum)
}

test("this is the required number of coins") {
    getMinAndDenom(null,4) should equal((-1,null))
    var a=getMinAndDenom(Array[Int](4),4)
    a._1 should equal (1)
    a._2(0) should equal (1)
    a._2.length should equal(1)
    getMinAndDenom(Array(2,3),50) should equal (17,Array(1,16))
    getMin(List(5,4,1),12) should equal (3)
}